package com.xj.algorithm.leetcode;

import java.util.*;

/**
 * 第三大的数
 */
public class L414_第三大的数 {

    /**
     * 给定一个非空数组，返回此数组中第三大的数。如果不存在，则返回数组中最大的数。要求算法时间复杂度必须是O(n)。
     * <p>
     * 示例 1:
     * <p>
     * 输入: [3, 2, 1]
     * <p>
     * 输出: 1
     * <p>
     * 解释: 第三大的数是 1.
     * 示例 2:
     * <p>
     * 输入: [1, 2]
     * <p>
     * 输出: 2
     * <p>
     * 解释: 第三大的数不存在, 所以返回最大的数 2 .
     * 示例 3:
     * <p>
     * 输入: [2, 2, 3, 1]
     * <p>
     * 输出: 1
     * <p>
     * 解释: 注意，要求返回第三大的数，是指第三大且唯一出现的数。
     * 存在两个值为2的数，它们都排第二。
     */
    public static void main(String[] args) {
        int[] nums = new int[]{3, 2, 1};
        System.out.println(thirdMaxGood(nums));

        int[] nums2 = new int[]{1, 2};
        System.out.println(thirdMaxGood(nums2));

        int[] nums3 = new int[]{2, 2, 3, 1};
        System.out.println(thirdMaxGood(nums3));

        int[] nums4 = new int[]{1, 2, 2, 5, 3, 5};
        System.out.println(thirdMaxGood(nums4));

        int[] nums5 = new int[]{1, 2, -2147483648};
        System.out.println(thirdMaxGood(nums5));
    }

    //自己的解法；每次取出1个数后，就比较4个数的大小,关键的数据结构set，统计个数
    public static int thirdMax(int[] nums) {
        int max = Integer.MIN_VALUE;
        int second = Integer.MIN_VALUE;
        int third = Integer.MIN_VALUE;

        Set<Integer> set = new HashSet<>();

        int len = nums.length;
        for (int i = 0; i < len; i++) {
            set.add(nums[i]);
            if (nums[i] > max) {
                third = second;
                second = max;
                max = nums[i];
            } else if (nums[i] > second && nums[i] != max) {
                third = second;
                second = nums[i];
            } else if (nums[i] > third && nums[i] != second && nums[i] != max) {
                third = nums[i];
            }
        }
        if (set.size() < 3) {
            return max;
        }
        return third;
    }

    //精彩解法：红黑树的数据结构，或者使用Long类型比较大小，当然也可以3次循环，每次找一个最大值
    //set.last()表示最大值, set.first()表示最小值
    public static int thirdMaxGood(int[] nums) {
        if (nums == null || nums.length == 0) throw new RuntimeException("error");
        TreeSet<Integer> set = new TreeSet<>();
        for (Integer elem : nums) {
            set.add(elem);
            if (set.size() > 3) set.remove(set.first());
        }
        return set.size() < 3 ? set.last() : set.first();
    }
}
